package _18_剑指OfferII;

public class _017_剑指OfferII含有所有字符的最短字符串 {

    public static void main(String[] args) {
        _017_剑指OfferII含有所有字符的最短字符串 v = new _017_剑指OfferII含有所有字符的最短字符串();

        String str1 = "ADOBECODEBANC";
        String str2 = "ABC";
        System.out.println(v.minWindow(str1, str2));

    }

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen < tLen) return "";
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        int[] containers = new int[58];
        for (int i = 0; i < tLen; i++) {
            containers[tChars[i] - 'A']++;
        }

        int minStart = 0;
        int minLen = sLen + 1;

        int left = 0;
        // 遍历子串
        for (int right = 0; right < sLen; right++) {
            containers[sChars[right] - 'A']--;
            // 是否以及存在最小覆盖子串
            if (existCoverStr(containers)) {
                // left向右扩展
                while (++containers[sChars[left++] - 'A'] <= 0);
                int len = right - left + 2;
                if (len < minLen) {
                    minLen = len;
                    minStart = left - 1;
                }
            }
        }
        return minLen == sLen + 1? "": new String(sChars, minStart, minLen);
    }

    private boolean existCoverStr(int[] containers) {
        for (int container : containers) {
            if (container > 0) return false;
        }
        return true;
    }

}
